package com.roc.learn.goodgoodstudy.algorithms;

/**
 * 选择排序
 * O(n2)
 */
public class SelectionSort {

    public static void main(String[] args) {
        int[] array = {6, 5, 4, 3, 2, 1};
        int[] array2 = {6, 5, 4, 3, 2, 1};
        SelectionSort(array);
        System.out.println("----");
        SelectionSort2(array2);
    }

    /**
     * 教学
     */
    public static void SelectionSort(int[] array) {
        if (array.length == 0) {
            return;
        }
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;

            for (int a : array) {
                System.out.print(a + ",");
            }
            System.out.println();
        }
    }

    public static void SelectionSort2(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int maxIndex = 0;
            for (int j = 0; j < array.length - i; j++) {
                if (array[j] > array[maxIndex]) {
                    maxIndex = j;
                }
            }
            // 把max值与本次循环的末尾交换
            int max = array[maxIndex];
            array[maxIndex] = array[array.length - 1 - i];
            array[array.length - 1 - i] = max;
        }
    }

    /**
     * 获取最小值的索引
     */
    public static Integer findSmallest(int[] array) {
        int smallest = array[0];
        int smallest_index = 0;
        for (int i = 1; i < array.length; i++) {
            if (array[i] < smallest) {
                smallest = array[i];
                smallest_index = i;
            }
        }
        return smallest_index;
    }

    /**
     * 练习1

     */


}
